Masala #1144

Rectangulariston mamlakati to’rtburchak shaklida bo’lib bizga \(H \times W\) to’rtburchakni eslatadi, ya’ni, bu mamlakat xaritasiga qaralganda \(H\) ta qator va \(W\) ta ustundan iborat mahallalardan iborat bo’lib, \(i\) - qatorning \(j\) - ustundagi mahallaning ixtiyoriy nuqtasi dengiz sathidan \(A_{i, j}\) balandlikda joylashgan.

Mamlakat prezidenti mamlakat uzra juda katta o’zgarishlar qilmoqchi. U biron bir  \(k(1 \le k < W)\) - ustunni tanlaydi va xaritadan qaraganda mamlakatni  \(k\) va \(k + 1\) - ustunlar orasidan daryo o’tkazadi. Shundan so’ng u mahallalarni birlashtiradi, agarda: mahallar o’zaro qo’shni(umumiy tomonga ega), dengiz sathidan bir xil balandlikda joylashgan hamda ularni yaqindagina o’tkazilgan dengiz ajratmasa.

Rectangulariston mamlakati prezidenti o’z rejalarini bajarib bo’lganidan so’ng mamlakatda erishish mumkin bo’lgan minimal mahallalar sonini aniqlang.

Kirish oqimining dastlabki satrida ikkita butun son, \(H(1 \le H)\)  va \(W(2\le W)\) sonlari beriladi. Keyingi \(H\) ta qatorning har birida \(W\) tadan butun son, \(A_{i,j}(1\le i \le H, 1 \le j \le W, 1 \le A_{i, j} \le 10^9)\) har bir mahallaning dengiz sathidan balandligi kiritiladi. Bunda matritsa elementlar soni \(H \times W \le 500000\) ekanligi kafolotlanadi.

Chiqish oqimida yagona butun son, Rectangulariston mamlakati prezidenti o’z rejalarini bajarib bo’lganidan so’ng mamlakatda erishish mumkin bo’lgan eng kam mahallalar sonini chop eting.